package arithmetic;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * 时间复杂度
 * 空间复杂度
 * 算法之~
 * 使用范围
 */
@Slf4j
public class BinaryInsertSort {

    public static void main(String[] args) {
        int[] a = {49, 38, 65, 97, 176, 213, 227, 49, 78, 34, 12, 164, 11, 18, 1};
        log.info("before sort:{}", Arrays.toString(a));
        sort(a);
        log.info("after sort:{}",Arrays.toString(a));
       // show(a);
    }

    private static void sort(int [] a){
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int left = 0;
            int right = i - 1;
            int mid = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp < a[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                a[j + 1] = a[j];
            }
            if (left != i) {
                a[left] = temp;
            }
        }
    }
}
